#include <iostream>

// 定义单链表节点结构 合并2个已排序的链表
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pHead1 ListNode类
     * @param pHead2 ListNode类
     * @return ListNode类
     */
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        // write code here
        if (pHead1 == nullptr) return pHead2;
        if (pHead2 == nullptr) return pHead1;
        // 虚拟头节点
        ListNode* dummy = new ListNode(-1);
        ListNode* cur = dummy;
        while (pHead1 && pHead2) {
            if (pHead1->val < pHead2->val) {
                cur->next = pHead1;
                // 移动指针
                pHead1 = pHead1->next;
            }
            else {
                cur->next = pHead2;
                // 移动指针
                pHead2 = pHead2->next;
            }
            cur = cur->next; // 指针后移
        }
        if (pHead1) cur->next = pHead1;
        else cur->next = pHead2;
        return dummy->next;
    }

    ListNode* Merge2(ListNode* pHead1, ListNode* pHead2) {
        // write code here
        if (pHead1 == nullptr) return pHead2;
        if (pHead2 == nullptr) return pHead1;
        // 虚拟头节点
        ListNode* dummy = new ListNode(-1);
        // 找到起始节点最小的链表
        if (pHead1->val > pHead2->val) {
            ListNode* temp = pHead1;
            pHead1 = pHead2;
            pHead2 = temp;
        }
        // 现在pHead是起始节点值最小的链表
        ListNode* ans = pHead1;
        while (pHead1->next && pHead2) {
            if (pHead1->next->val > pHead2->val) {
                // 插入pHead2到链表1
                ListNode* temp = pHead2->next;
                pHead2->next = pHead1->next;
                pHead1->next = pHead2;
                pHead2 = temp;
            }
            pHead1 = pHead1->next;
        }
        if (pHead1->next == nullptr) pHead1->next = pHead2;
        return ans;
    }
};

// 辅助函数：创建链表
ListNode* createList(int arr[], int n) {
    if (n == 0) return nullptr;
    ListNode* head = new ListNode(arr[0]);
    ListNode* cur = head;
    for (int i = 1; i < n; ++i) {
        cur->next = new ListNode(arr[i]);
        cur = cur->next;
    }
    return head;
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    ListNode* cur = head;
    while (cur) {
        std::cout << cur->val << " ";
        cur = cur->next;
    }
    std::cout << std::endl;
}

// 辅助函数：释放链表内存
void freeList(ListNode* head) {
    while (head) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}

int main() {
    // 创建两个有序链表
    int arr1[] = {1, 3, 5};
    int arr2[] = {2, 4, 6};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    int n2 = sizeof(arr2) / sizeof(arr2[0]);

    ListNode* pHead1 = createList(arr1, n1);
    ListNode* pHead2 = createList(arr2, n2);

    Solution solution;

    // 测试 Merge 方法
    ListNode* merged1 = solution.Merge(pHead1, pHead2);
    std::cout << "Merged list by Merge method: ";
    printList(merged1);
    freeList(merged1);

    // 重新创建链表进行 Merge2 方法测试
    pHead1 = createList(arr1, n1);
    pHead2 = createList(arr2, n2);
    ListNode* merged2 = solution.Merge2(pHead1, pHead2);
    std::cout << "Merged list by Merge2 method: ";
    printList(merged2);
    freeList(merged2);

    return 0;
}